package problem438;

//438.找到字符串中所有字母异位
//https://leetcode.cn/problems/find-all-anagrams-in-a-string/?envType=study-plan-v2&envId=top-100-liked

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        int n = s.length();
        int m = p.length();
        int size = 0;
        int[] hash1 = new int[128];
        int[] hash2 = new int[128];
        for(int i = 0; i<m; i++) {
            if(hash1[p.charAt(i)] == 0) size++;
            hash1[p.charAt(i)]++;
        }
        int count = 0;
        for(int i = 0, j = 0; j<n; j++) {
            hash2[s.charAt(j)]++;
            if(hash1[s.charAt(j)] == hash2[s.charAt(j)]) count++;

            if(j-i+1 >= m) {
                if(count == size) {
                    list.add(i);
                }
                if(hash1[s.charAt(i)] == hash2[s.charAt(i)]) {
                    count--;
                }
                hash2[s.charAt(i)]--;
                i++;
            }
        }
        return list;
    }
}